package com.yww.leetcode.binarysearchtree;

import com.yww.leetcode.common.TreeNode;

import java.util.LinkedList;
import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;

/**
 * @author yww
 * @description 98. 验证二叉搜索树
 * @since 2024/2/15 15:16
 */
public class IsValidBST98 {
    // 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    // 有效 二叉搜索树定义如下：
    // 节点的左子树只包含 小于 当前节点的数。
    // 节点的右子树只包含 大于 当前节点的数。
    // 所有左子树和右子树自身必须也是二叉搜索树。
    public boolean isValidBST(TreeNode root) {
        int i = new Random().nextInt();
        if ((i & 1) == 0) { // 偶数
            return upAndLowRecur(root, Long.MIN_VALUE, Long.MAX_VALUE);
        } else { // 奇数
            i = new Random().nextInt();
            if ((i & 1) == 0) {
                return recurInorder(root, new AtomicLong(Long.MIN_VALUE));
            } else {
                return inorder(root);
            }
        }
    }

    /**
     * 上下限递归解决
     * <ul>
     *     <li>设每个节点必须在一个范围内：(min, max)，不包含边界，若节点值超过这个范围，则返回 false</li>
     *     <li>对于 node.left 范围肯定是 (min, node.val)</li>
     *     <li>对于 node.right 范围肯定是 (node.val, max)</li>
     *     <li>一开始不知道 min，max 则取 java 中长整数的最小、最大值</li>
     *     <li>本质是前序遍历 + 剪枝</li>
     * </ul>
     */
    private boolean upAndLowRecur(TreeNode cur, Long min, Long max) {
        if (cur == null) {
            return true;
        }
        if (cur.val <= min || cur.val >= max) {
            return false;
        }
        boolean leftFlag = upAndLowRecur(cur.left, min, (long) cur.val);
        boolean rightFlag = upAndLowRecur(cur.right, (long) cur.val, max);
        return leftFlag && rightFlag;
    }

    /**
     * 中序遍历验证（递归）
     *
     * @param cur    当前节点
     * @param preVal 传入引用，不止作用与一个方法栈内
     */
    private boolean recurInorder(TreeNode cur, AtomicLong preVal) {
        if (cur == null) {
            return true;
        }
        boolean leftFlag = recurInorder(cur.left, preVal); // 左
        if (preVal.get() >= cur.val) {
            return false;
        }
        preVal.set(cur.val);
        boolean rightFlag = recurInorder(cur.right, preVal); // 右
        return leftFlag && rightFlag;
    }

    /**
     * 通过中序遍历进行验证（迭代）
     */
    private boolean inorder(TreeNode root) {
        TreeNode cur = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        long preVal = Long.MIN_VALUE;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left; // 左
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) {
                    // 中序遍历
                    if (preVal >= peek.val) { // 中序结果应该是从小到大（本题相等也不符合）
                        return false;
                    }
                    pop = stack.pop(); // 弹出
                    preVal = pop.val; // min更新
                    // 后序遍历
                } else if (peek.right == pop) {
                    pop = stack.pop(); // 弹出
                    // 后序遍历
                } else {
                    // 中序遍历
                    if (preVal >= peek.val) { // 中序结果应该是从小到大（本题相等也不符合）
                        return false;
                    }
                    preVal = peek.val; // min更新
                    cur = peek.right; // 右
                }
            }
        }
        return true;
    }

}
